import java.util.*;

public class Solution2 {

    /**
     * 寻找和最小的k对数字
     * @param num1
     * @param num2
     * @param k
     * @return
     */
    public List<List<Integer>> kSmallestPairs(int[] num1, int[] num2, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return (o2[0]+o2[1]) - (o1[0]+o1[1]);
            }
        });
        for (int i = 0; i < num1.length; i++) {
            for (int j = 0; j < num2.length; j++) {
                if (queue.size() < k) {
                    queue.offer(new int[]{num1[i],num2[j]});
                    continue;
                }
                int[] top = queue.peek();
                if ((top[0] + top[1]) > (num1[i] + num2[j])) {
                    queue.offer(new int[]{num1[i],num2[j]});
                    queue.poll();
                }else {
                    break;
                }
            }
        }
        List<List<Integer>> lists = new ArrayList<>();

        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int[] tmp = queue.poll();
            list.add(tmp[0]);
            list.add(tmp[1]);
            lists.add(list);
        }
        return lists;
    }

}
